11057. Важное научное число
Пин собирал свое
очень важное новое изобретение, но в какой-то момент он обнаружил, что ошибся в
одной из формул и мог собрать соответствующую деталь неправильно.
Внимательно
посмотрев на деталь и исправив формулу, Пин отметил, что сейчас в детали стоят
две шестеренки с a и b зубцами соответственно, а работать
правильно она будет с шестеренками размеров a + x и b + x
соответственно, где x – неотрицательное целое число такое, что a
+ x делится на b и b + x делится на a.
Пин очень устал, поэтому просит помочь ему
найти такое неотрицательное x, удовлетворяющее заданным условиям.
Поскольку Пин не любит большие шестеренки, из всех подходящих значений x
следует выбрать минимальное.
Вход. В одной строке
заданы два числа a и b (1 ≤ a, b ≤ 109)
– размеры шестеренок в детали.
Выход. Выведите одно
целое неотрицательное число x – минимальное количество зубцов, которых не хватает в
шестеренках, чтобы изобретение работало правильно.
|
Пример
входа 1 |
Пример
выхода 1 |
|
8 1 |
7 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
3 4 |
5 |
|
|
|
|
Пример
входа 3 |
Пример
выхода 3 |
|
123 123 |
0 |
НОД,
НОК
Нам известно что:
·
a + x делится на b;
·
b + x делится на a;
Следовательно a + b + x делится и на a и на b. Или то же самое что a + b + x делится на lcm
= НОК(a, b). Существует такое k, что a + b + x = k * lcm.
В качесстве значения x
возьмем lcm – a – b. Однако если это число
отрицательное, тогда возьмем x = 2 *
lcm – a – b. Очевидно,
что a + b ≤ 2 * lcm.
Пример
Рассмотрим второй пример, где a
= 3, b = 4. lcm
= НОК(3, 4) = 12.
Ответом будет значение x
= lcm – a – b = 12 – 3 – 4 = 5.
В третьем примере a
= 123, b = 123. lcm = НОК(123, 123) = 123.
Значение x = lcm – a – b = 123 –
123 – 123 = -123 отрицательно. Тогда в качестве ответа возьмем x
= 2 * lcm – a – b = 2 * 123 – 123 – 123 = 0.
Реализация алгоритма
Функция gcd вычисляет наибольший общий делитель чисел a и b.
long long gcd(long long a, long long b)
{
return (!b) ? a : gcd(b, a % b);
}
Читаем входные данные.
cin >> a >> b;
Вычисляем lcm = НОК(a, b) = (a * b) / НОД(a, b).
lcm = a / gcd(a, b) * b;
Вычисляем ответ.
res = lcm - a - b;
if (res
< 0) res += lcm;
Выводим ответ.
cout << res << endl;